package com.lxm.leetcode;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

/**
 * 给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 个最小元素（从 1 开始计数）。
 * <p>
 *  
 * <p>
 * 示例 1：
 * <p>
 * <p>
 * 输入：root = [3,1,4,null,2], k = 1
 * 输出：1
 * 示例 2：
 * <p>
 * <p>
 * 输入：root = [5,3,6,2,4,null,null,1], k = 3
 * 输出：3
 *  
 * <p>
 *  
 * <p>
 * 提示：
 * <p>
 * 树中的节点数为 n 。
 * 1 <= k <= n <= 104
 * 0 <= Node.val <= 104
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/kth-smallest-element-in-a-bst
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Question230 {

    /**
     * 利用二叉搜索树中序遍历有序性特性
     * @param root
     * @param k
     * @return
     */
    public int kthSmallest(TreeNode root, int k) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        int rank = 1;
        while (!stack.isEmpty() || cur != null) {
            if (cur != null) {
                stack.push(cur);
                cur = cur.left;
            } else {
                cur = stack.pop();
                if (rank == k) {
                    return cur.val;
                }
                rank++;
                cur = cur.right;
            }
        }
        return 0;
    }

    /**
     * DFS中序遍历解决
     * @param root
     * @param k
     * @return
     */
    int rank = 1;
    Map<String, Integer> result = new HashMap<>(1);

    public int kthSmallestDFS(TreeNode root, int k) {
        traverse(root, k);
        return result.get("result");
    }


    private void traverse(TreeNode root, int k) {
        if (root == null || rank > k) {
            return;
        }
        traverse(root.left, k);
        if (rank == k && result.isEmpty()) {
            result.put("result", root.val);
            return;
        }
        rank++;
        traverse(root.right, k);
    }

    public static void main(String[] args) {
        TreeNode l3 = new TreeNode(2, null, null);
        TreeNode l2_1 = new TreeNode(1, null, l3);
        TreeNode l2_2 = new TreeNode(4, null, null);
        TreeNode l1 = new TreeNode(3, l2_1, l2_2);
        Question230 test =new Question230();
        System.out.println(test.kthSmallestDFS(l1,1));
    }
}
